package leetcode;

import java.util.*;

/**
 * Created by lyk on 2017/3/31.
 * Package name: leetcode
 * Porject name: untitled1
 */
public class RepeatedDNASequences {
    public static void main(String[] args) {
        RepeatedDNASequences rs = new RepeatedDNASequences();
        System.out.println(rs.findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"));
    }

    public List<String> findRepeatedDnaSequences(String s) {
        List<String> result = new ArrayList<String>();

        int len = s.length();
        if (len < 10) {
            return result;
        }

        Map<Character, Integer> map = new HashMap<Character, Integer>();
        map.put('A', 0);
        map.put('C', 1);
        map.put('G', 2);
        map.put('T', 3);

        Set<Integer> temp = new HashSet<Integer>();
        Set<Integer> added = new HashSet<Integer>();

        int hash = 0;
        for (int i = 0; i < len; i++) {
            if (i < 9) {
                //each ACGT fit 2 bits, so left shift 2
                hash = (hash << 2) + map.get(s.charAt(i));
            } else {
                hash = (hash << 2) + map.get(s.charAt(i));
                //make length of hash to be 20
                hash = hash &  (1 << 20) - 1;

                if (temp.contains(hash) && !added.contains(hash)) {
                    result.add(s.substring(i - 9, i + 1));
                    added.add(hash); //track added
                } else {
                    temp.add(hash);
                }
            }

        }

        return result;
    }
//    public List<String> findRepeatedDnaSequences(String s) {
//        Set seen = new HashSet(), repeated = new HashSet();
//        for (int i = 0; i + 9 < s.length(); i++) {
//            String ten = s.substring(i, i + 10);
//            if (!seen.add(ten))
//                repeated.add(ten);
//        }
//        return new ArrayList(repeated);
//    }
}
